// MaxSubBST.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

#define null 0
struct TreeNode
{
    int value;
    TreeNode *left, *right;

    TreeNode() { };

    TreeNode(int v)
    {
        value=v;
        left=right=null;
    };
};

// Given a binary tree, find its sub-BST that has the maximum number of nodes.
//
// Algorithm:
//   1. Post-Order traverse and validate the tree. For each visiting node, calculate the number of nodes on its left child and right respectively
//   2. If p->left is BST and leftCount > maxCount, maxBSTRoot = p->left
//   3. If p->right is BST and rightCount > maxCount, maxBSTRoot = p->right
//   4. If p is BST and leftCount+rightCount+1 > maxCount, maxBSTRoot = p
// Analysis:
//   Time Complexity: O(n)
//   Space Complexity: O(logn)

bool ValidateBST(TreeNode *node, int &min, int &max, int &count, TreeNode *&maxBSTRoot, int &maxCount)
{
    if(!node)
    {
        count=0;
        return true;
    }

    int leftMin,leftMax,leftCount;
    leftMin=leftMax=node->value;
    bool isLeftBST=ValidateBST(node->left,leftMin,leftMax,leftCount,maxBSTRoot,maxCount);

    int rightMin,rightMax,rightCount;
    rightMin=rightMax=node->value;
    bool isRightBST=ValidateBST(node->right,rightMin,rightMax,rightCount,maxBSTRoot,maxCount);

    if(isLeftBST && maxCount<leftCount)
    {
        maxBSTRoot=node->left;
        maxCount=leftCount;
    }

    if(isRightBST && maxCount<rightCount)
    {
        maxBSTRoot=node->right;
        maxCount=rightCount;
    }

    count=leftCount+rightCount+1;
    min=leftMin;
    max=rightMax;

    if(isLeftBST && isRightBST && ((!node->left||leftMax<node->value)&&(!node->right||rightMin>node->value)))
    {
        if(maxCount<count)
        {
            maxBSTRoot=node;
            maxCount=count;
        }
        return true;
    }
    else
    {
        return false;
    }
}

TreeNode *MaxSubBST(TreeNode *root)
{
    if(!root) return null;
    int min,max,count,maxCount=0;
    TreeNode *maxBSTRoot=null;
    ValidateBST(root,min,max,count,maxBSTRoot,maxCount);
    return maxBSTRoot;
}

int _tmain(int argc, _TCHAR* argv[])
{
    return getchar();
}